package ai.遗传算法;

import javax.xml.crypto.Data;
import java.util.*;

/**
 * 使用遗传算法找到y=x2在[0,31]上的最大值
 */
public class 遗传算法 {
//    //适应度函数
//    private String fx;

    //种群规模
    private int N;

    //交叉率
    private float Pc;

    //变异率
    private float Pm;

    //代数
    private int T;

    //种群，这里要计算y=x2上的最大值，因为基因这里用二进制表示了，为了方便就用字符串型
    private ArrayList<String> S;

    //这个是x，而这里真正的种群是y，就是x2，这里为了计算适应度方便，就存储起来了，其实不存储也可以，但是浪费时间
    private ArrayList<Integer> preS;

    //适应度f()
    private ArrayList<Integer> f;

    public 遗传算法(int n, float pc, float pm) {
        N = n;
        Pc = pc;
        Pm = pm;
        T = 0;
        S = new ArrayList<>();
        preS = new ArrayList<>();
        f = new ArrayList<>();
    }

    /**
     * 生成初始种群
     */
    private void init(){
        //组成一个初始种群
        Random random = new Random();
        for (int i = 0; i < N; i++){
            //保证生成的随机数都在0-32之间
            int randomInt = Math.abs((int)(random.nextDouble() * 10000) % 32);

            preS.add(randomInt);
            S.add(Integer.toBinaryString(randomInt));
        }
        //代数 = 1
        T = 1;

//        while (true) {
            if (!calculateF())
            chooseAndCopy();
//            System.out.println(Arrays.toString(preS.toArray()));
//        }
    }

    /**
     * 计算适应度
     * @return 是否已经有目标：这里的目标就是找到最大值，即11111（31）
     */
    private boolean calculateF(){
        for (int i = 0; i < N; i++){
            f.add(i, preS.get(i) * preS.get(i));

        }
        //如果已经找到最大，就结束遗传算法
        return f.contains(31 * 31);
    }

    /**
     * 选择-复制
     */
    private void chooseAndCopy(){
        //选择概率
        double[] chooseProbability = new double[N];
        //随机生成的0-1之间的概率
        double[] randomProbability = new double[N];
        //种群的适应度总和
        int sumF = 0;
        Random random = new Random();
        for (int i = 0;i < N; i++){
            sumF += f.get(i);
            //顺便把概率也随机出来
            //震惊！nextDouble()居然只生成0-1的小数，得来全不费工夫
            randomProbability[i] = random.nextDouble();
        }
        //积累概率，为什么是N+1?因为需要在第一个位置存放0
        double[] chooseProbabilitySum = new double[N+1];
        //计算选择概率
        for (int i = 0; i < N; i++){
            System.out.println(preS.get(i));
            System.out.println(f.get(i) + " " + sumF);
            chooseProbability[i] = (double) f.get(i) / sumF;
            if (0 == i) chooseProbabilitySum[i+1] = chooseProbability[i];
            else chooseProbabilitySum[i+1] = chooseProbabilitySum[i] + chooseProbability[i];
        }
        //每一个的被选择的次数
        int[] count = new int[N];
        //计算被选择的次数
        for (int i = 0; i < N; i++){
            //看一看生成的随机数在哪个范围内
            for (int j = 1; j <= N; j++){
                //如果它在积累概率的某两个的范围之内，就说明这个染色体被选择了
                System.out.println(chooseProbability[i]);
                System.out.println(chooseProbabilitySum[j]);
                System.out.println(chooseProbabilitySum[j-1]);
                System.out.println("---");
                if (randomProbability[i] <= chooseProbabilitySum[j] && randomProbability[i] >= chooseProbabilitySum[j-1]) {
                    count[j-1]++;
                    break;
                }
            }
        }

        //开始选择和淘汰染色体
        ArrayList<Integer> newPreS = new ArrayList<>();
        ArrayList<String> newS = new ArrayList<>();
        //更新种群
//        System.out.println(Arrays.toString(count));
        for (int i = 0; i < N ;i++){
            for (int j = 0; j < count[i]; j++){
                int siInt = preS.get(i);
                newPreS.add(siInt);
                newS.add(Integer.toBinaryString(siInt));
            }
        }
        preS.clear();
        preS.addAll(newPreS);
        S.clear();
        S.addAll(newS);
    }

    public static void main(String[] args) {
        遗传算法 yc = new 遗传算法(5, 0.1f, 0.1f);
        yc.init();
    }
}
